1. Field of the Invention
The present invention relates to a device of synthesizing a program with a function of pointers and dynamic allocation/deallocation, and a method of synthesizing a program with a function of pointers and dynamic allocation/deallocation.
2. Description of the Related Art
Different languages have been used as input to high-level synthesis. Hardware Description Languages (HDLs), such as Verilog HDL and VHDL, are the most commonly used. However, designers often write system-level models using programming languages, such as C or C++, to estimate the system performance and verify the functional correctness of the design. Using C/C++ offers higher-level of abstraction, fast simulation as well as the possibility of leveraging a vast amount of legacy code and libraries, which facilitates the task of system modeling.
The use of C/C++ or a subset of C/C++ to describe both hardware and software would accelerate the design process and facilitate the software/hardware migration. Designers could describe their system using C. The system would then be partitioned into software and hardware blocks, implemented using synthesis tools. The new SystemC initative is an attempt to standardize a C/C++-based language for both hardware and software design.
C was originally designed to develop the UNIX operating system. It provides constructs to directly access memory (through pointers) and to manage memories and I/O using the standard C library (malloc, free, . . . ). These constructs are widely used in software. Nevertheless, many of the networking and multimedia applications implemented in hardware or mixed hardware/software systems are also using complex data structures stored in one or multiple memory banks. As a result, many of the C/C++ features which were originally designed for software applications are now making their way into hardware.
In order to help designers refine their code from a simulation model to a synthesizable behavioral description, this inventors are trying to efficiently synthesize the full ANSI C standard. This task turns out to be particularly difficult because of dynamic memory allocation/deallocation, function calls, recursions, goto""s, type castings and pointers.
In the past few month, different synthesis tools have been announced to ease the mapping of C code into hardware (Abhijit Ghosh, Joachim Kunkel, Stan Liao, xe2x80x9cHardware Synthesis from C/C++,xe2x80x9d proceedings of the Design, Automation and Test in Europe DATE""99, pp.387-389, Munich, 1999.), (Kazutoshi Wakabayashi, xe2x80x9cC-based Synthesis with Behavioral Synthesizer, Cyber,xe2x80x9d proceedings of the Design, Automation and Test in Europe DATE""99, pp.390-391, Munich, 1999.). And other many more companies and research projects work on synthesis of hardware from C. All of these tools support a subset of the language (e.g. restrictions on pointers, function calls, etc.). In particular, they do not support dynamic memory allocation/deallocation using the ANSI standard library functions malloc and free
In this inventors tool SpC (Luc Semeria, Giovanni De Micheli, xe2x80x9cSpC: Synthesis of Pointers in C.Application of Pointer Analysis to the Behavioral Synthesis from Cxe2x80x9d, proceedings of the International Conference on Computer-Aided Design ICCAD""98, pp.321-326, San Jose, November 98.), pointer variables are resolved at compile-time to synthesize c functional models in hardware efficiently. In description of the preferred embodiment, this inventors will focus on an implementation of dynamic memory allocation/deallocation (malloc, free) in hardware. By definition, in general, storage for dynamically allocated data structures cannot be assigned at compile time. The synthesis of C code involving dynamic memory allocation/deallocation requires access to some allocation and deallocation primitives implemented either in software, as in an operating system, or in hardware.
Dynamic memory allocation/deallocation is tightly coupled with pointers and the notion of a single address space. Pointer dereferences (load, stores, etc.) as well as memory allocation/deallocation are all referring to a main memory. However, in application-specific hardware, designers may want to optimize the memory architecture by using register banks, multiple memories etc. Therefore, memory allocations may be distributed onto multiple memories and pointers may reference data stored in registers, memories or even wires (e.g. output of a functional unit). To enable efficient mapping of C code with pointers and malloc""s into hardware, the synthesis tool has to automatically generate the appropriate circuit to dynamically allocate, access (read/write) and deallocate data. Memory management as well as accurate pointers resolution are key features for C-based synthesis. They are enablers for the efficient design of applications involving complex data structures.
The contribution of description of the preferred embodiment is to present a solution for efficiently mapping arbitrary program code with pointers and dynamic allocation allocation/deallocation into hardware. This solution fits current memory management methodologies. It consists of instantiating a hardware allocator tailored to an application and a memory architecture. This work also supports the resolution and optimization of pointers without restriction on the data structures.
For decades, memory management has been one of the major development area both for software and computer architecture. In software, at the user-level, memory management is typically performed by the operating system. In hardware, memory bandwidth is often a bottleneck in applications such as networking, signal processing, graphics and encryption. Memory architecture exploration and efficient memory management technology are key to the design of new high-performance systems. Memory generators commercially available today enable fast integration of memories in a system. Scheduling of memory accesses has also been integrated into most commercial high level synthesis (ELS) tools. Most of the refinement and compilations steps developed for software applications can also be used for hardware. Nevertheless, a software methodology usually assumes a fixed memory architecture which may be general purpose or application specific like in a DSP or ASIP. In hardware, at the behavioral level, designers would typically explore different memory architectures in order to trade-off area and power for a given timing constraint.
A few projects and tools have recently been announced to ease the mapping of C models into hardware. In practice, current tools don""t support dynamic memory allocation/deallocation and have restriction on pointers"" usage (Giovanni De Micheli , xe2x80x9cHardware Synthesis from c/c++,xe2x80x9d in the proceeding of the Design, Automation and Test in Europe DATE""99, pp.382-383, Munich, 1999.). SpC , enables the behavioral synthesis of C code with pointer variables to variables and arrays. In description of the preferred embodiment, this inventors present how pointers in general (e.g. array of pointers, pointers in structures, pointers to structures etc.) and dynamic memory allocation/deallocation can also be efficiently synthesized.
A methodology for the design of custom memory systems has been described by Catthoor et al. (Francky Catthoor, Sven Wuytack, Eddy De Greef, Florin Balasa, Lode Nachtergaele, Arnout Vandecappelle, xe2x80x9cCustom Memory Management Methodology,xe2x80x9d Kluwer Academic Publishers, Dordrecht, June 98.). It is defined for two sets of applications, networking and signal processing, and supports a limited subset of C/C++. The basic concepts presented in Catthoor""s work can be generalized to support a larger subset of the C syntax for an extended set of applications. Two main steps can be distinguished in the methodology: this inventors describe briefly here the transformations performed first at the system level, and then at the architectural level.
At the system level, the functionality of the algorithm is verified. Data formats are refined. For example, after quantization, the format of data can be refined from floating-point to fixed-point (H. Keding, M. Willems, M. Coors, H. Meyr, xe2x80x9cFRIDGE: A Fixed-Point Design And Simulation Environment,xe2x80x9d proceedings of the Design Automation and Test in Europe DATE""98, pp.429-435, 1998.). Data structures can also be refined for example to reduce the number of indirect memory references. Examples of such transformations for networking applications have been studied by Wuytack et al. in (Sven Wuytack, Julio da Silva Jr., Francky Catthoor, Gjalt de Jong, Chantal Ykman, xe2x80x9cMerrory Management for Embedded Network Applications,xe2x80x9d transactions on Computer Aided Design, Volume 18, number 5, pp. 533-544, May 99.), (Sven Wuytack, Francky Catthoor, Hugo De Man, xe2x80x9cTransforming set data types to power optimal data structures,xe2x80x9d IEEE Transactions on Computer Aided Design, pp.619-629, June 1996.).
At the architectural level, after partitioning, the system typically consists of multiple communicating processes to be mapped to hardware or software (Abhijit Ghosh, Joachim Kunkel, Stan Liao, xe2x80x9cHardware Synthesis from C/C++,xe2x80x9d proceedings of the Design, Automation and Test in Europe DATE""99, pp.387-389, Munich, 1999.). Memory segments are defined for internal storage and/or shared memory. These memory segments can then be mapped to one or multiple memories during synthesis. Some of the storage area (e.g. internal variables, etc.) can be statically allocated during synthesis or compilation. However, to support dynamic storage allocation/deallocation (e.g. for recursive data structures), allocation and deallocation primitives implemented in software or hardware shall be defined.
In software, memory allocation and deallocation are implemented as primitives part of the operating system (OS). These primitives can be called in a C program using the functions defined in the standard library (e.g. malloc, free, etc.) Many schemes have been developed for OS to manage memory. An extensive survey of the techniques used for memory allocation and deallocation can be found in (Paul Wilson, Mark Johnstone, David Doles, xe2x80x9cDynamic Storage Allocation: A Survey and Critical Review,xe2x80x9d presented at Int. Workshop Memory Management, Kinross, Scotland, September 95.).
Memory management can also be implemented in hardware. For memory allocation and deallocation, instead of the system calls to the OS, requests are sent through signals to an allocator block (AKA. virtual memory manager) implemented in hardware. Its interface is shown on FIG. 10. Internally, the allocator stores a list of the free blocks in memory as well as a list of the allocated blocks. To allocate memory, the size of the block to be allocated (malloc_size) is sent. The allocator then searches in its free list a big enough block and returns the address of the beginning of this block (malloc_address). Two techniques are often used: first fit where the first acceptable free block is returned or best fit where the block of minimal size is returned. To free previously allocated memory, the address of the block to be deallocated (free_address) is sent to the allocator. The allocator then searches inside of the allocated list the block and adds it back to the free list. Adjacent free blocks can then be merged. The implementation itself of the allocator can vary according to the application and the data structures. A number of these implementations are presented by Wuytack et al. (Sven wuytack, Jullio da Silva Jr., Francky Catthoor, Gjalt de Jong, Chantal Ykman, xe2x80x9cMemory Management for Embedded Network Applications,xe2x80x9d transactions, on Computer Aided Design, Volume 18, number 95, pp. 533-544, May 99.), (J. Morris Chang, Edward R. Gehringer xe2x80x9cA High-Performance Memory Allocator for Object-Oriented Systems,xe2x80x9d IEEE trans. on Computers, vol. 45, no. 3, march 96.).
FIG. 10 is a diagram for explaining the interface of the allocator block implementing malloc and free functions.
Once an architecture is decided, hardware can be implemented using synthesis tools and compilers can be used for software. As far as memory management is concerned, memory accesses scheduling, register/memory allocation and address generation can be integrated into synthesis tools and compilers. The latest development for hardware synthesis have been presented by Catthoor et al (Francky Catthoor, Sven Wuytack, Eddy De Greef, Florin Balasa, Lode Nachtergaele, Arnout Vandecappelle, xe2x80x9cCustom Memory Management Methodology,xe2x80x9d Kluwer Academic Publishers, Dordrecht, June 98.) and Panda et al. (Preeti Ranjan Panda, Nikil D.Dutt, Alexandru Nicolau, xe2x80x9cMemory Issues in Embedded Systems-On-Chip Optimizations and Exploration,xe2x80x9d Kluwer Academic Pub, October 1998.).
This contribution fits in the methodology described above. In particular, this inventors present techniques to automate the synthesis of program code with pointers and dynamic memory allocation/deallocation into hardware. The outcome of this research is a tool that maps and optimizes hardware models in program code with pointers and dynamic memory allocation/deallocation into verilog HDL synthesizable by commercially available synthesis tools.
It is an object of the present invention to provide the circuit synthesis method of synthesizing the semiconductor circuit of executing the program containing pointer and dynamic allocation/deallocation.
According to the first aspect of the invention, a circuit synthesis method of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising the steps of:
resolving pointer and dynamic allocation in the code of the program; and
changing the code of the program into the code which does not contain the pointer and the dynamic allocation;
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation.
In the preferred construction, the program is C-language program.
In another preferred construction, the circuit synthesis method further comprising
a step of changing the code changed by the resolution step into the code of Hardware Description Languages, and
a step of synthesizing the semiconductor circuit based on the code of Hardware Description Languages.
In another preferred construction, the resolution step
including a step of checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a step of performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a step of replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out.
According to the second aspect of the invention, a circuit synthesis method of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising the steps of:
resolving pointer and dynamic allocation in the code of the program; and
changing the code of the program into the code which does not contain the pointer and the dynamic allocation; and
the resolution step including
a step of checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a step of performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a step of replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out,
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation.
According to the third aspect of the invention, a circuit synthesis method of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising the steps of:
resolving pointer and dynamic allocation in the code of the program; and
changing the code of the program into the code which does not contain the pointer and the dynamic allocation; and
the resolution step including
a pointer analysis step of finding pointer variable in the code, and checking the information on the variable which substitutes an address to each pointer variable,
a step of executing variable declaration of a structure object comprising a variable tag and a integer variable index in the code after the conversion corresponding to each pointer variable, which variable tag shows the kind of variable substituted to a pointer variable, and which integer variable index records the addition-and-subtraction processing in the code to the pointer variable,
a step of replacing the command which substitutes the address of other variables to the pointer variable in the code with the command which substitutes the information on the kind of other variables to the variable tag and substitutes value xe2x80x9c0xe2x80x9d to the variable index,
a step of replacing the command which fluctuates the value of the pointer variable in the code with the command which fluctuates the value of the variable index of the structure object corresponding to the pointer variable,
a step of replacing the command which refers to the address shown by the pointer variable with the command which refers to the value of the arrangement position of the value of the variable index in the variable shown by the variable tag,
a step of checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a step of performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a step of replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out,
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation.
In another preferred construction, the circuit synthesis method further comprising
recording the number of block allocated to block of the pointer variable,
accessing the block by specifying the number of block in free area by allocator,
wherein synthesizing the semiconductor circuit which executes management of optimized free area.
In another preferred construction, the resolution step including
when the size of the variable to be allocated has to be constant, and dynamically-allocated variable have to be both allocated and deallocated within the same unbounded loop,
a step of performing beforehand statically variable declaration of the array variable which is the same size as the dynamically-allocated variable in the converted code,
a step of replacing the command which performs dynamic allocation with the command which references the variable to the array variable by which variable declaration was carried out,
a step of removing the command performs dynamic deallocation in the code.
According to another aspect of the invention, a circuit synthesis system of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising:
a means for resolving pointer and dynamic allocation in the code of the program; and
a means for changing the code of the program into the code which does not contain the pointer and the dynamic allocation;
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation
In another preferred construction, the program is C-language program.
In another preferred construction, the circuit synthesis system further comprising
a means for changing the code changed by the resolution meaning into the code of Hardware Description Languages, and
a means for of synthesizing the semiconductor circuit based on the code of Hardware Description Languages.
In another preferred construction, the resolution meaning including
a means for checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a means for performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a means for replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out.
According to another aspect of the invention, a circuit synthesis system of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising:
a means for resolving pointer and dynamic allocation in the code of the program; and
a means for changing the code of the program into the code which does not contain the pointer and the dynamic allocation; and
the resolution meaning including
a means for checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a means for performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a means for replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out,
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation.
According to another aspect of the invention, a circuit synthesis system of a semiconductor circuit for executing a program with a function of pointers and dynamic allocation, comprising:
a means for resolving pointer and dynamic allocation in the code of the program; and
a means for changing the code of the program into the code which does not contain the pointer and the dynamic allocation; and
the resolution meaning including
a pointer analysis means for finding pointer variable in the code, and checking the information on the variable which substitutes an address to each pointer variable,
a means for executing variable declaration of a structure object comprising a variable tag and a integer variable index in the code after the conversion corresponding to each pointer variable, which variable tag shows the kind of variable substituted to a pointer variable, and which integer variable index records the addition-and-subtraction processing in the code to the pointer variable,
a means for replacing the command which substitutes the. address of other variables to the pointer variable in the code with the command which substitutes the information on the kind of other variables to the variable tag and substitutes value xe2x80x9c0xe2x80x9d to the variable index,
a means for replacing the command which fluctuates the value of the pointer variable in the code with the command which fluctuates the value of the variable index of the structure object corresponding to the pointer variable,
a means for replacing the command which refers to the address shown by the pointer variable with the command which refers to the value of the arrangement position of the value of the variable index in the variable shown by the variable tag,
a means for checking the kind of the variable which is the object of dynamic allocation and the quantity of a memory assigned in the code,
a means for performing beforehand variable declaration of the variable which is the object of the dynamic allocation statically in the converted code,
a means for replacing the command which performs dynamic allocation in the code with the command which gives the pointer to the variable by which variable declaration was carried out,
wherein synthesizing the semiconductor circuit which executes the program with a function of pointers and dynamic allocation.
Other objects, features and advantages of the present invention will become clear from the detailed description given herebelow.